package leecode

func pathSumLCR(root *TreeNode, targetSum int) int {
	var result int
	if root == nil {
		return result
	}
	result = backtrackingLCR(root, targetSum)
	result += pathSumLCR(root.Left, targetSum)
	result += pathSumLCR(root.Right, targetSum)
	return result
}

func backtrackingLCR(node *TreeNode, targetSum int) int {
	var result int
	if node == nil {
		return result
	}
	targetSum = targetSum - node.Val
	if targetSum == 0 {
		result++
	}
	result += backtrackingLCR(node.Left, targetSum)
	result += backtrackingLCR(node.Right, targetSum)
	targetSum = targetSum + node.Val
	return result
}
